using System;

public class TriBox
{
  private static int X = 0;
  private static int Y = 1;
  private static int Z = 2;
  private static float[] v0 = { 0, 0, 0 };
  private static float[] v1 = { 0, 0, 0 };
  private static float[] v2 = { 0, 0, 0 };
  private static float p0 = 0;
  private static float p1 = 0;
  private static float p2 = 0;
  private static float min = 0;
  private static float max = 0;
  private static float rad = 0;
  private static float[] boxhalfsize = { 0, 0, 0 };

  private static void CROSS(float[] dest, float[] v1, float[] v2)
  {
    dest[0]=v1[1]*v2[2]-v1[2]*v2[1];
    dest[1]=v1[2]*v2[0]-v1[0]*v2[2];
    dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
  }

  private static float DOT(float[] v1, float[] v2)
  {
    return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];
  }

  private static void SUB(float[] dest, float[] v1, float[] v2)
  {
    dest[0]=v1[0]-v2[0];
    dest[1]=v1[1]-v2[1];
    dest[2]=v1[2]-v2[2];
  }

  private static void FINDMINMAX(float x0, float x1, float x2, ref float min, ref float max)
  {
    min = max = x0;
    if(x1<min) min=x1;
    if(x1>max) max=x1;
    if(x2<min) min=x2;
    if(x2>max) max=x2;
  }

  private static int planeBoxOverlap(float[] normal, float d, float[] maxbox)
  {
    int q;
    float[] vmin = {0, 0, 0};
    float[] vmax = {0, 0, 0};

    for(q=X;q<=Z;q++)
    {
      if(normal[q]>0.0f)
      {
        vmin[q]=-maxbox[q];
        vmax[q]=maxbox[q];
      }
      else
      {
        vmin[q]=maxbox[q];
        vmax[q]=-maxbox[q];
      }
    }

    if(DOT(normal,vmin)+d>0.0f) return 0;
    if(DOT(normal,vmax)+d>=0.0f) return 1;
  
    return 0;
  }

  /*======================== X-tests ========================*/
  private static int AXISTEST_X01(float a, float b, float fa, float fb)
  {
    p0 = a*v0[Y] - b*v0[Z];
    p2 = a*v2[Y] - b*v2[Z];

    if(p0<p2)
    {
      min=p0;
      max=p2;
    }
    else
    {
      min=p2;
      max=p0;
    }

    rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  private static int AXISTEST_X2(float a, float b, float fa, float fb)
  {
    p0 = a*v0[Y] - b*v0[Z];
    p1 = a*v1[Y] - b*v1[Z];

    if(p0<p1)
    {
      min=p0;
      max=p1;
    }
    else
    {
      min=p1;
      max=p0;
    }

    rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  /*======================== Y-tests ========================*/
  private static int AXISTEST_Y02(float a, float b, float fa, float fb)
  {
    p0 = -a*v0[X] + b*v0[Z];
    p2 = -a*v2[X] + b*v2[Z];

    if(p0<p2)
    {
      min=p0;
      max=p2;
    }
    else
    {
      min=p2;
      max=p0;
    }

    rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  private static int AXISTEST_Y1(float a, float b, float fa, float fb)
  {
    p0 = -a*v0[X] + b*v0[Z];
    p1 = -a*v1[X] + b*v1[Z];

    if(p0<p1)
    {
      min=p0;
      max=p1;
    }
    else
    {
      min=p1;
      max=p0;
    }

    rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  /*======================== Z-tests ========================*/
  private static int AXISTEST_Z12(float a, float b, float fa, float fb)
  {
    p1 = a*v1[X] - b*v1[Y];
    p2 = a*v2[X] - b*v2[Y];

    if(p2<p1)
    {
      min=p2;
      max=p1;
    }
    else
    {
      min=p1;
      max=p2;
    }

    rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  private static int AXISTEST_Z0(float a, float b, float fa, float fb)
  {
    p0 = a*v0[X] - b*v0[Y];
    p1 = a*v1[X] - b*v1[Y];

    if(p0<p1)
    {
      min=p0;
      max=p1;
    }
    else
    {
      min=p1;
      max=p0;
    }

    rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];

    if(min>rad || max<-rad)
    {
      return 0;
    }

    return 1;
  }

  public static int triBoxOverlap(float[] boxcenter, float[] boxhalfsize, float[][] triverts)
  {
    float fex = 0;
    float fey = 0;
    float fez = 0;
    float d = 0;
    float[] normal = { 0, 0, 0 };
    float[] e0 = { 0, 0, 0 };
    float[] e1 = { 0, 0, 0 };
    float[] e2 = { 0, 0, 0 };
  
    TriBox.boxhalfsize = boxhalfsize;

    /* This is the fastest branch on Sun */
    /* move everything so that the boxcenter is in (0,0,0) */
    SUB(v0,triverts[0],boxcenter);
    SUB(v1,triverts[1],boxcenter);
    SUB(v2,triverts[2],boxcenter);

    /* compute triangle edges */
    SUB(e0,v1,v0);      /* tri edge 0 */
    SUB(e1,v2,v1);      /* tri edge 1 */
    SUB(e2,v0,v2);      /* tri edge 2 */

    /* Bullet 3:  */
    /*  test the 9 tests first (this was faster) */
    fex = Math.Abs(e0[X]);
    fey = Math.Abs(e0[Y]);
    fez = Math.Abs(e0[Z]);
    if(AXISTEST_X01(e0[Z], e0[Y], fez, fey) == 0){return 0;};
    if(AXISTEST_Y02(e0[Z], e0[X], fez, fex) == 0){return 0;};
    if(AXISTEST_Z12(e0[Y], e0[X], fey, fex) == 0){return 0;};

    fex = Math.Abs(e1[X]);
    fey = Math.Abs(e1[Y]);
    fez = Math.Abs(e1[Z]);
    if(AXISTEST_X01(e1[Z], e1[Y], fez, fey) == 0){return 0;};
    if(AXISTEST_Y02(e1[Z], e1[X], fez, fex) == 0){return 0;};
    if(AXISTEST_Z0(e1[Y], e1[X], fey, fex) == 0){return 0;};

    fex = Math.Abs(e2[X]);
    fey = Math.Abs(e2[Y]);
    fez = Math.Abs(e2[Z]);
    if(AXISTEST_X2(e2[Z], e2[Y], fez, fey) == 0){return 0;};
    if(AXISTEST_Y1(e2[Z], e2[X], fez, fex) == 0){return 0;};
    if(AXISTEST_Z12(e2[Y], e2[X], fey, fex) == 0){return 0;};

    /* Bullet 1: */
    /*  first test overlap in the {x,y,z}-directions */
    /*  find min, max of the triangle each direction, and test for overlap in */
    /*  that direction -- this is equivalent to testing a minimal AABB around */
    /*  the triangle against the AABB */
  
    /* test in X-direction */
    FINDMINMAX(v0[X],v1[X],v2[X], ref min, ref max);
    if(min>boxhalfsize[X] || max<-boxhalfsize[X]) return 0;

    /* test in Y-direction */
    FINDMINMAX(v0[Y],v1[Y],v2[Y], ref min, ref max);
    if(min>boxhalfsize[Y] || max<-boxhalfsize[Y]) return 0;
  
    /* test in Z-direction */
    FINDMINMAX(v0[Z],v1[Z],v2[Z], ref min, ref max);
    if(min>boxhalfsize[Z] || max<-boxhalfsize[Z]) return 0;

    /* Bullet 2: */
    /*  test if the box intersects the plane of the triangle */
    /*  compute plane equation of triangle: normal*x+d=0 */
    CROSS(normal,e0,e1);
    d=-DOT(normal,v0);  /* plane eq: normal.x+d=0 */

    if(planeBoxOverlap(normal,d,boxhalfsize) == 0)
    {
      return 0;
    }

    return 1;   /* box and triangle overlaps */
  }
}

